Written Test

------------



Q - Given a dictionary, Write algorithms for the following.

    # Find if a word exists in the dictionary or no.

    # Given a word, print all the words in the dictionary that starts with that word.



Expain the datastucture and the algo with the space and time complexity?



Q - Given n cities and k houses in each city. A postman has to deliver letters to at least m houses in each city. Given the distance between the cities and the houses, write an algo for the postman to deliver the letters with minimum distance. (Travelling salesman problem)



Q - A log processing question. Given some huge log files. Find out the number of time a particular user has logged in.





Technical Round -1

------------------



Q - Given a String, find out all the permutation of the strings? Time complexity? Handle duplicate characters. AAA should only give AAA. Write Code.



Q - Given a BST, prove that its in-order traversal is always sorted and Given a binary tree, if its in-order traversal is sorted proof that it is a BST



Q - Given an array containing 0s,1s,2s. Sort the array without using counting sort. Write Code.



Q - Given an sorted array and an number n. Find out an element k in the array such that Max(k) < n. Write Code.



Technical Round - 2 

-------------------



Q - Given a sorted array that contains 0s and 1s. find out the first occurrence of 1. Write Code.



Q - Given an acyclic graph of a city where each edge represents a road in the city and each vertex represents an crossing. Write an algo to find out the minimum number of vertices at which a policemen will be kept so that all the roads are covered. If a policeman is kept at a vertex then all the edges connected to that vertex is said to be covered.



Tell the data structure you will be using to store the graph. and the algo with time and space complexity. 



Technical Round -3 

------------------



Q - Given a singly linked list find out if there is a loop exists. If yes, what is the starting point. 

Proof it mathematically.



Q - Pre-process a dictionary in a way that later on given a string in the dictionary, output all the strings in the dictionary that are anagrams to the given string.

Data structure used. Time and space complexity.



Q - Given a binary tree, check whether it is a BST or not.

Write the algo. Time and space complexity.



Bar Raiser

----------



Mostly HR questions.

Question on designing a schema and then a SQL query.

Question on amazon website. What you like and dislike.

testing questions. Testing a new look for the site. how should that be done. HOw to find out if the customer really likes the new look or not.



Manager Round

-------------



Q - Design a lift system. OOPs concept.



Q - Given two string a and b. FInd out the minimum length substring k of a such that k contains all the characters of b. Minimum window problem.



Again some HR questions.

HAVE YOUR SAY...